#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

int zhi(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return 0;
        }
    }
    return 1;
}

int main() {
    int n;
    scanf("%d", &n);
    int m = zhi(n);
    if (m) {
        printf("1");
    }
    else if (n % 2 != 0) {
        printf("3");
    }
    else {
        printf("2");
    }
    return 0;
}